package com.dbh.alg.algorithm.important;


import com.dbh.alg.algorithm.hot100.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
 * <p>
 *
 *
 * 示例 1:
 * <p>
 *
 * 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 * 输出: [3,9,20,null,null,15,7]
 * 示例 2:
 * <p>
 * 输入: preorder = [-1], inorder = [-1]
 * 输出: [-1]
 * <p>
 *
 * 提示:
 * <p>
 * 1 <= preorder.length <= 3000
 * inorder.length == preorder.length
 * -3000 <= preorder[i], inorder[i] <= 3000
 * preorder 和 inorder 均 无重复 元素
 * inorder 均出现在 preorder
 * preorder 保证 为二叉树的前序遍历序列
 * inorder 保证 为二叉树的中序遍历序列
 */
public class Leetcode105_从前序与中序遍历序列构造二叉树 {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null ||preorder.length == 0) {
            return null;
        }
        // 创建根节点
        TreeNode root = new TreeNode(preorder[0]);
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);

        // 中序遍历的当前索引
        int inorderIndex = 0;

        // 遍历前序序列剩余元素
        for (int i = 1; i < preorder.length; i++) {
            // 当前待构建的节点值
            int currentVal = preorder[i];
            // 查看栈顶节点（不弹出）
            TreeNode topNode = stack.peek();

            // 情况1：栈顶节点与中序当前值不匹配
            // 说明当前值属于栈顶节点的左子树
            if (topNode.val != inorder[inorderIndex]) {
                topNode.left = new TreeNode(currentVal);
                stack.push(topNode.left);  // 新节点入栈（继续构建左子树）
            }
            // 情况2：栈顶节点与中序当前值匹配
            // 说明栈顶节点无左子树（或左子树已构建完毕）
            else {
                // 回溯栈：弹出所有已匹配中序值的节点
                // 最后一次弹出的节点即为当前值的父节点
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    topNode = stack.pop();  // 弹出已处理节点
                    inorderIndex++;         // 移动中序索引（标记该节点已处理）
                }
                // 将当前值作为最后弹出节点的右子树
                topNode.right = new TreeNode(currentVal);
                stack.push(topNode.right);  // 新节点入栈（继续构建右子树）
            }
        }
        return root;
     }

}
